package main

import (
	"sort"
)

func main() {

}

/*
*
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

注意：所有供暖器 heaters 都遵循你的半径标准，加热的半径也一样。

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置 1, 4 上有两个供暖器。我们需要将加热半径设为 1，这样所有房屋就都能得到供暖
*/

// 找每个房子就近的供暖器，取最大值
func findRadius(houses []int, heaters []int) int {
	// 先排序
	// 目的是为了房屋方便选择就近的供暖器
	sort.Ints(houses)
	sort.Ints(heaters)
	var ans int

	for i, j := 0, 0; i < len(houses); i++ {
		for !best(houses, heaters, i, j) {
			j++
		}
		ans = max(ans, abs(heaters[j]-houses[i]))
	}
	return ans
}

// i号房屋，j号供暖器是否是最优解
// i号房屋选择j号供暖器，或者i号房屋选择j+1号供暖器
func best(houses, heaters []int, i, j int) bool {
	if j == len(heaters)-1 {
		return true
	}
	// < 则说明当前j号供暖器对于i号房屋来说是最近的，j后面的必定更远
	return abs(houses[i]-heaters[j]) < abs(houses[i]-heaters[j+1])
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return 0 - a
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
